1. Field of the Invention
The present invention relates to intra-domain traffic engineering. More specifically, embodiments of the present invention relate to improved methods and systems for intra-net traffic routing.
2. Description of the Related Art
Because of the increasing cost and complexity of large operational internet protocol (IP) networks, traffic engineering has become important in recent years. Good traffic engineering can significantly improve the management and performance of operational IP networks while reducing costs. Prior art traffic engineering was based on a solid understanding of traffic flows when designing and configuring traffic routing protocols.
It has been widely accepted in the traffic engineering community that a good understanding of the traffic matrix (TM) and the dynamics of traffic flows can lead to better utilization of link capacities through better traffic routing. Theoretically, if the TM is exactly known, then an optimal traffic routing can be obtained by solving the corresponding multi-commodity flow problem instance, reference D. Mitra and K. G. Ramakrishna, “A Case Study of Multiservice, Multipriority Traffic Engineering Design for Data Networks,” Proceedings of IEEE GLOBECOM, pages 1077-1083, IEEE 1999. Based on the TM it is possible to establish link weights, that being the percentage of traffic routed through a particular link in a network of link and nodes between an origin-destination pair, that can be tuned to yield near-optimal utilization.
Unfortunately, measuring and predicting traffic demands are illusive problems. Flow measurements are rarely available on all links and Egress/Ingress points of the network. It is even harder to obtain a good picture of Origin-Destination (OD) flow aggregates. Moreover, traffic demands change over time, both in the short term and in the long term, and are subject to special events or failures, either internal or external to the network. Despite recently developed models and measurement tools that enable extrapolation and estimation of traffic demands, it appeared that the best to hope for was an approximate picture of demand, and not necessarily a very good or very current one.
Even if current traffic demands are known, their dynamic nature poses a challenge: while it is desirable to modify the routing to be highly efficient for the current traffic demands, modifying the traffic routing can potentially cause disruptions in service due to path changes and convergence times while the system reaches a consistent state.
This basic premise, however, never seems to have been quantified: just how important is accurate knowledge of traffic demands to obtaining good network utilization? Since traffic demands are dynamic and illusive, an optimal routing solution at one time could be a poor routing solution at another, and adjusting the routing presents multiple issues. That poses a question: is it possible, possibly better, to obtain a robust routing that guarantees a nearly optimal utilization based on only a fairly limited knowledge of the applicable traffic demands?
Good traffic engineering would seem to call for a design that is robust under a wide range of conditions. That is, a routing that can perform nearly optimally for a wide range of traffic demands. Thus methods of and systems for routing traffic in a nearly optimal way over a wide range of traffic demands and that handles link failures well would be highly useful.